package alo;

/**
 * @ClassName LCS
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/20 22:24
 * @Version 1.0
 */
public class LCS {
    public String LCS(String str1, String str2) {
        if (str1 == null || str2 == null) return "-1";
        int n1 = str1.length(), n2 = str2.length();
        if (n1 == 0 || n2 == 0) return "-1";
        int[][] dp = new int[n1 + 1][n2 + 1];

        int maxLen = 0, x = 0;
        for (int i = 1; i <= n1; i++) {
            char ch1 = str1.charAt(i - 1);
            for (int j = 1; j <= n2; j++) {
                char ch2 = str2.charAt(j - 1);
                if (ch1 == ch2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        x = i;
                    }
                }
            }
        }

        return maxLen == 0 ? "-1" : str1.substring(x - maxLen, x);
    }
}
